package com.mlh.binarytree;

public class TrieTree {

	//节点
	public static class TrieNode{
		public int pass;//多少个单词经过这个节点
		public int end;//有多少个单词以这个节点为结尾
		public TrieNode[] nexts;//表示下一节点 这不是二叉树 不要以为只有两个节点

		public TrieNode(){
			pass=0;
			end=0;
			nexts=new TrieNode[26];//这边26代表有26个字母
		}
	}

	//前缀树
	public static class Trie{
		private TrieNode root;
		public Trie(){
			root=new TrieNode();
		}

		//将单词插入到前缀树中的方法
		public void insert(String word){
			if(word==null){
				return;
			}
			//将单词拆分成字符数组
			char[]chs=word.toCharArray();
			//每个单词都会经过root pass++
			root.pass++;
			TrieNode node=root;
			//index表示字母的ascll码值
			int index=0;
			for(int i=0;i<chs.length;i++){
				//第一步计算字母的ascll
				index=chs[i]-'a';
				//要查看节点的nexts下面有没有已经存在的字母  有则复用  没有则创建
				if(node.nexts[index]==null){
					node.nexts[index]=new TrieNode();
				}
				node=node.nexts[index];
				node.pass++;
			}
			node.end++;
		}

		//查询前缀树中是否有某个单词
		public int search(String word){
			if(word==null){
				return 0;
			}
			char[]chs=word.toCharArray();
			int index=0;
			TrieNode node=root;
			for (int i=0;i<chs.length;i++){
				index=chs[i]-'a';
				if(node.nexts[index]==null){
					//表示没有通往该单词的路
					return 0;
				}
				node=node.nexts[index];
			}
			//还要判断到最后一个字母的时候 end是否大于0
			if(node.end==0){
				return 0;
			}
			return 1;
		}

		//删除前缀树中的单词
		public void delete(String word){
			if(word==null){
				return;
			}
			//假如要删除的单词并不在前缀树中，则直接返回即可
			if(search(word)==0){
				return;
			}
			//要删除一个单词  要修改pass的值还要end的值
			//注意当修改后pass=0时，这个节点就可以置为null，因为没有单词经过这个节点了
			TrieNode node=root;
			TrieNode temp;//用于将下一节点置为null;
			root.pass--;
			int index=0;
			char[]chs=word.toCharArray();
			for(int i=0;i<chs.length;i++){
				index=chs[i]-'a';
				temp=node;
				node=node.nexts[index];
				node.pass--;
				if(node.pass==0){
					temp.nexts[index]=null;
					return;
				}
				node.end--;
			}
		}

		//查找前缀有prefix的单词有多少个
		public int prefixNumber(String prefix){
			if(prefix==null){
				return 0;
			}
			TrieNode node=root;
			char[]chs=prefix.toCharArray();
			int index=0;
			for(int i=0;i<chs.length;i++){
				index=chs[i]-'a';
				if(node.nexts[index]==null){
					return 0;
				}
				node=node.nexts[index];
			}
			return node.pass;
		}
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		trie.insert("zuo");
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuoa");
		trie.insert("zuoac");
		trie.insert("zuoab");
		trie.insert("zuoad");
		trie.delete("zuoa");
		System.out.println(trie.search("zuoa"));
		System.out.println(trie.prefixNumber("zuo"));

	}

}
